﻿using System;
using System.Collections;
using System.Text;


namespace SpeakerRecognition
{
    public class PamClustering
    {
        private static double[,] lastDisMat = null; //variable that containg the last calculated distance matrix
        /// <summary>
        /// This property returns the last dissimilarity matrix used by the pam clustering
        /// The set option is not yet available
        /// </summary>
        public static double[,] LastDisMatCalculated
        {
            get { return PamClustering.lastDisMat; }
            set {   }
        }
        private static double MedoidMin = 0.0;//variable that contain a Min sum of Build step of the Pam aslgorithm
        private static ArrayList Indxarr = new ArrayList();
        /// <summary>
        /// Empty constructor
        /// </summary>
        public PamClustering()
        {
        }
        /******** The first Step of Build Pam*******************************/
        private static void SumDistance(double[,] Dismat)
        {
            double sum = 0.0, minMedoid = 0.0;// minMedoid: variable that contain the min sum of Medoid
            int flag = 1, minIndx = 0;
            int szrow =Dismat.GetUpperBound(0)+1; 
            for (int i = 0; i < szrow  ; i++)
            {
                sum = 0.0;
                for (int j = 0; j < szrow; j++)
                {
                    sum += Dismat[i, j];
                }
                if (flag == 1)
                {
                    minMedoid = sum;
                    minIndx = i;
                    flag = 0;
                }
                Dismat[i, szrow] = sum;
                if (sum <= minMedoid)
                {
                    minMedoid = sum;
                    minIndx = i;
                }
            }
            Dismat[minIndx, szrow + 1] = 1;//if Medoid or Not   
            Indxarr.Add(minIndx);
            ///**************Print the Distance Matrix*******************/
            //printDisMat(Dismat);
        }
        private static void BuildSwap(double[,] Dismat,  int Indx, int flagIndx,int clusternumber)
        {
            double Sum = 0.0, min = 0.0, MinSum = MedoidMin;
            int TempIndx = 0;
            int szrow = Dismat.GetUpperBound(0) + 1;  
            for (int i = 0; i < szrow; i++)
            {

                if (Dismat[i, szrow + 1] != 1)
                {
                    Sum = 0.0;
                    for (int j = 0; j < szrow; j++)
                    {
                        min = Dismat[i, j];
                        // System.Console.Out.WriteLine( min);
                        for (int m = 0; m < szrow; m++)
                        {
                            if (Dismat[m, szrow + 1] == 1 && flagIndx == 1)
                            {                                
                                if (Dismat[m, j] <= min)
                                {
                                    min = Dismat[m, j];

                                }                               
                            }
                            else//SwapStep
                            {

                                if (Dismat[m, szrow + 1] == 1 && m != Indx)
                                {                                  
                                    if (Dismat[m, j] <= min)
                                    {                                 
                                        min = Dismat[m, j];
                                    }
                                }
                            }
                        }
                        Sum += min;
                    }
                    Dismat[i, szrow] = Sum;
                    if (flagIndx == 2 && Sum < MedoidMin)
                    {
                        MinSum = Sum;
                        TempIndx = i;

                    }                    
                }
            }
            if (flagIndx == 2)
            {
                if (MinSum < MedoidMin)
                {
                    MedoidMin = MinSum;
                    Dismat[TempIndx, szrow + 1] = 1;
                    Dismat[Indx, szrow + 1] = 0;
                    Indxarr[clusternumber]=TempIndx;  

                }
            }
        }

        /*********The Build Step Of Pam**************************/
        private static void BuildStep(double[,] Dismat,  int K)
        {
            double minMedoid = 0.0;
            int minIndx = 0, flag = 1;
            int szrow = Dismat.GetUpperBound(0) + 1;   
            for (int k = 0; k < K - 1; k++)
            {
                BuildSwap(Dismat, -1, 1,-1);
                flag = 1;
                /**************Find the next Medoid******************/
                for (int n = 0; n < szrow; n++)
                {
                    if (flag == 1)
                    {
                        minMedoid = Dismat[n, szrow];
                        minIndx = n;
                        flag = 0;
                    }
                    else
                    {
                        if (Dismat[n, szrow] <= minMedoid)
                        {
                            minMedoid = Dismat[n, szrow];
                            minIndx = n;
                        }
                    }
                }
                Dismat[minIndx, szrow + 1] = 1;
                Indxarr.Add(minIndx);
            }
            MedoidMin = Dismat[minIndx, szrow];
            ///////**************Print the Distance Matrix*******************/
            //printDisMat(Dismat);
        }
        /*********The Swap Step Of Pam**************************/
        public static void SwapStep(double[,] Dismat,  int K)
        {

            int szrow = Dismat.GetUpperBound(0) + 1; 
            for (int i = 0; i < K; i++)
            {
                BuildSwap(Dismat, int.Parse(Indxarr[i].ToString()), 2,i);
            }

            ///////**************Print the Distance Matrix*******************/
            //printDisMat(Dismat);
        }


 

    //////////////////////////////////////////////////////////////////////////////
    //EXTENSION TO PAM CLASS BY AMIT EITAN 24.3.2009
    //////////////////////////////////////////////////////////////////////////////
        /// <summary>
        /// This method performs pam clustering on a collection of vectors
        /// </summary>
        /// <param name="inputVectors">Array list containing arrays of double (the vectors as double[])</param>
        /// <param name="numberOfClusters">number of disired cluster</param>
        /// <param name="distance">the distance mesurment unit to use</param>
        /// <returns>Array list contining arrays of int. each array is a cluster, the numbers  in the array are the index of the inputvectors in the Array list </returns>
        public static ArrayList execute(ArrayList inputVectors,int numberOfClusters, DistanceMeasurement distance)
        {
            double[,] disMat = calcDistMatrix(inputVectors, distance);
            Indxarr.Clear();
            //////////////
            //BUILD STEP//
            //////////////
            SumDistance(disMat);
            //Pam.printDisMat(disMat);

            BuildStep(disMat, numberOfClusters);
            //Console.WriteLine("BUILD STEP");
            //Pam.printDisMat(disMat);
            
            /////////////
            //SWAP STEP//
            /////////////
            //Console.WriteLine("SWAP STEP");
            //Pam.printDisMat(disMat);
            SwapStep(disMat, numberOfClusters);
            lastDisMat = disMat;
          //  printDisMat(disMat);
            return PamClustering.clusteredDisMatToCluserIndexArrays(disMat);
        }

        /// <summary>
        /// This method calculates the distance metrix between vectors
        /// </summary>
        /// <param name="inputVectors">ArrayList of vectors to calculate (array list of double[])</param>
        /// <param name="distance">the enm of the distance function to be used</param>
        /// <returns>disimilarity matrix of the vectors with two extra colums for sum and mediod calculations</returns>
        private static double[,] calcDistMatrix(ArrayList inputVectors, DistanceMeasurement distance)
        {
            int rowCount = inputVectors.Count;
            Distance pamDistance = new Distance();
            pamDistance.DistanceMethod = distance;
            double[,] disMat = new double[rowCount, rowCount + 2]; //create a matrix for the dissimilarity
            double tempDist;
            for (int row = 0; row < rowCount; row++) //go Over all the rows
            {
                for (int col = row; col < rowCount; col++) //go over upper diagnol
                {
                    if (row == col) //the distance is 0
                    {
                        disMat[row, col] = 0;
                    }
                    else //calculate the distances between vectors and update disMat
                    {
                        tempDist = pamDistance.calculatDistance((double[])inputVectors[row], (double[])inputVectors[col]);
                        disMat[row, col] = tempDist;
                        disMat[col, row] = tempDist;
                    }
                }
            }
            return disMat;
        }
        /// <summary>
        /// This method converts the clustered distance matrix to array list of
        /// int[] each int[] represents a cluster and holds the indexes of the elements
        /// belonging to it
        /// </summary>
        /// <param name="disMat">disimilarity matrix to analize</param>
        /// <returns>Array list of int[] holding representing the clusters holding indexes</returns>
        private static ArrayList clusteredDisMatToCluserIndexArrays(double [,] disMat)
        {
            
            int rowCount = disMat.GetUpperBound(0) + 1;
            int numberOfClusters = Indxarr.Count;

            ArrayList[] clusters = new ArrayList[numberOfClusters]; //This will temporarly store array lists each representing a cluster
            for (int i = 0; i < numberOfClusters; i++)
            {
                clusters[i] = new ArrayList(); //each array list represts a cluster and will store idexes of that cluster
            }

            for (int row = 0; row < rowCount; row++)//go over all rows
            {
                int minDistClusterIndex = 0;//iniial minDistIndex to one of the mediods
                double minDist = disMat[row, (int)Indxarr[0]]; //init row min val
                foreach (int col in Indxarr) //go over all arraylist that holds indexes of mediods
                {
                    if (disMat[row, col] < minDist) //find to wich mediod this row belongs
                    {
                        minDistClusterIndex = Indxarr.IndexOf(col);
                        minDist = disMat[row, col];
                    }
                }
                clusters[minDistClusterIndex].Add(row);
            }
            //Convet from Array of arraylists to an ArrayList of int Arrays

            ArrayList resultClusters = new ArrayList(numberOfClusters);

            foreach (ArrayList cluster in clusters)
            {
                int[] indexes = new int[cluster.Count]; //crete an array with correct size
                for(int i=0; i<cluster.Count; i++)
                {
                    if (Indxarr.Contains(cluster[i])&&i>0)
                    {
                        int temp = indexes[0];
                        indexes[0] = (int)cluster[i];
                        indexes[i] = temp;
                    }
                    else
                        indexes[i] = (int)cluster[i];
                }
                resultClusters.Add(indexes);
            }




            return resultClusters;

        }
        /// <summary>
        /// This method print's to screen a dissimalrity matrix
        /// </summary>
        /// <param name="disMat">dissimilarity matrix to print</param>
        private static void printDisMat(double[,] disMat)
        {
            int rowCount = disMat.GetUpperBound(0) + 1;
            for (int row = 0; row < rowCount; row++)
            {
                Console.Write("LINE " + row + ": ");
                for (int col = 0; col < rowCount; col++)
                {
                    Console.Write("[");
                    Console.Write("{0:F}", disMat[row, col]);
                    Console.Write("] ");
                }
                Console.Write("   SUM = ");
                Console.Write("{0:F}", disMat[row, rowCount]); //print sum
                if (disMat[row, rowCount + 1] == 1) //print if it's a mediod
                {
                    Console.Write("   MEDOID ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();
        }
        public static void pamUnitTest()
        {
                            ArrayList vectors = new ArrayList();
                int vectorSize = 2;
                int numberOfVectors = 4;
                int count = 0;
                for (int i=0; i<numberOfVectors; i++) //Generate vectors
                {
                    double[] newVec = new double[vectorSize]; //create a new vector
                    for (int j=0; j<vectorSize; j++) //fill vector with values
                    {
                        newVec[j] = count++; 
                    }
                    vectors.Add(newVec); //add the new vec to list
                }
                
                //double[,] disMat = Pam.calcDistMatrix(vectors, DistanceMeasurement.EuclidianDistance);
                double [,] disMat = initMatrixForTest();
                SumDistance(disMat);
                printDisMat(disMat);
                Console.WriteLine("BUILD STEP");
                BuildStep(disMat,2);
                printDisMat(disMat);
                Console.WriteLine("SWAP STEP");
                SwapStep(disMat, 2);
                printDisMat(disMat);
                Console.WriteLine("Get Clusters");
                ArrayList clsteringRes = clusteredDisMatToCluserIndexArrays(disMat);
                for (int i=0; i < clsteringRes.Count; i++)
                {
                    Console.Write("CLUSTER " + (i+1)+":\t");

                    foreach (int index in (int[])clsteringRes[i]) //go over all the index in the array
                    {
                        Console.Write(index + ",");
                    }
                    Console.WriteLine();
                }

        }
        private static double[,] initMatrixForTest()
        {
            double[,] disMat = new double[5, 7];
            disMat[0, 1] = 8;
            disMat[0, 2] = 8;
            disMat[0, 3] = 7;
            disMat[0, 4] = 7;
            disMat[1, 2] = 0.5;
            disMat[1, 3] = 4;
            disMat[1, 4] = 4;
            disMat[2, 3] = 4;
            disMat[2, 4] = 3;
            disMat[3, 4] = 1;
            int rowCount = disMat.GetUpperBound(0) + 1;
            for (int row = 0; row < rowCount; row++) //go Over all the rows
            {
                for (int col = row; col < rowCount; col++) //go over upper diagnol
                {
                    if (row == col) //the distance is 0
                    {
                        disMat[row, col] = 0;
                    }
                    else //calculate the distances between vectors and update disMat
                    {
                        disMat[col, row] = disMat[row, col];
                    }
                }
            }
            return disMat;
        }
        /******END OF PAM UNIT TEST METHODS***************/
        //////////////////////////////////////////////////////////////////////////////
        ///END OF EXTENSION///////////////////////////////////////////////////////////
        //////////////////////////////////////////////////////////////////////////////
    }

    
}
